/*
 * @lc app=leetcode.cn id=160 lang=java
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * Accepted
    39/39 cases passed (1 ms)
    Your runtime beats 98.18 % of java submissions
    Your memory usage beats 51.75 % of java submissions (44.3 MB)
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA, pb = headB;
        while (pa != null && pb != null) {
            if (pa == pb)
                return pa;

            pa = pa.next;
            pb = pb.next;

            if (pa == null && pb == null) {
                return null;
            } else if (pa == null) {
                pa = headB;
            } else if (pb == null) {
                pb = headA;
            }
        }
        return null;
    }
}
// @lc code=end
